package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * 45. 跳跃游戏 II
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/21 17:24
 */
public class Jump {
    public int jump(int[] nums) {
        int length = nums.length;
        if (length < 3) {
            return length - 1;
        }
        int max = 0;
        int s = 0;
        int next = nums[0];
        for (int i = 0; i < length; i++) {
            next = Math.max(next, nums[i] + i);

            if (next >= length - 1) {
                return s + 1;
            }

            if (i == max) {
                s++;
                max = next;
            }
        }


        return s;
    }
}
